package 中等.搜索.深度优先搜索;

import java.util.ArrayList;
import java.util.List;

/**
 * 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和
 * 上边界，而 “大西洋” 处于大陆的右边界和下边界。
 * 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ，
 *  heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
 * 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北
 * 、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
 * 返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格
 * (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
 */
public class 太平洋大西洋水流问题_417 {

    public static void main(String[] args) {

        int[][] heights = {{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}};
        System.out.println(new 太平洋大西洋水流问题_417().pacificAtlantic(heights));

    }

    /**
     * 遍历+深度搜索
     * 遍历每个节点判断是否能同时流入两大海洋，会有许多重复判断
     * 逆序思维，从岛屿边缘，从低到高流入岛屿，左上方流入的岛屿格子标记，
     * 右下方的岛屿也做标记，同时拥有两个标记符合条件
     *
     * @param heights
     * @return
     */
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        rows = heights.length;
        columns = heights[0].length;
        int[][] pacific = new int[rows][columns];
        int[][] atlantic = new int[rows][columns];

        for (int column = 0; column < columns; column++) {
            search(0, column, pacific);
        }
        for (int row = 0; row < rows; row++) {
            search(row, 0, pacific);
        }
        for (int column = 0; column < columns; column++) {
            search(rows - 1, column, atlantic);
        }
        for (int row = 0; row < rows; row++) {
            search(row, columns - 1, atlantic);
        }

        List<List<Integer>> lists = new ArrayList<>();
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (pacific[row][column] == 1 && atlantic[row][column] == 1) {
                    List<Integer> list = new ArrayList<>();
                    list.add(row);
                    list.add(column);
                    lists.add(list);
                }
            }
        }
        return lists;
    }

    private int[][] heights;

    private int rows, columns;

    private int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    private void search(int row, int column, int[][] ocean) {
        // 走过了
        if (ocean[row][column] == 1) return;
        ocean[row][column] = 1;
        for (int[] direct : direction) {
            int nextRow = row + direct[0];
            int nextColumn = column + direct[1];
            if (nextRow >= 0 && nextRow < rows && nextColumn >= 0 && nextColumn < columns) {
                if (heights[nextRow][nextColumn] >= heights[row][column]) {
                    search(nextRow, nextColumn, ocean);
                }
            }
        }
    }

}
